/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package Controle;

import Entidades.Link;
import Entidades.No;
import Entidades.LocalizadoraDeNos;
import Entidades.LocalizadoraLinks;
import java.util.ArrayList;

/**
 *
 * @author Adriano
 */
public class A_Estrela {
    private static limite.Apresentacao tela;
    private static ArrayList<No> abertos = null;
    private static ArrayList<No> fechados = null;

    // implementa o algoritmo A estrela
    public static ArrayList<No> AEstrela(No origem, No destino) {
        // cria lista de abertos e a lista de fechados
        abertos=new ArrayList();
        fechados=new ArrayList();
        //adiciona o nó de origem na lista de abertos
        abertos.add(origem);
        //inicia origem
        // coloca o predecessor como "null" para identificar que este nó é a origem
        // no momento em que o caminho estiver sendo reconstruido
        origem.setPredecessor(null);
        // a distância acumulado é 0 pois não houve nenhum movimento antes do nó de origem.
        origem.setDistanciaAcumulada(0);
        //calcula a euristica de todos os nós até o destino(H)
        ControleNos.calculaEuristicas(destino);
        No noAtual=null;
        while (noAtual != destino) {
            //se a lista de abertos for vazia, não foi possível encontrar o caminho entre esses dois nós
            if (abertos.size() == 0) {
                return null;
            }
            // retira primeiro elementos da lista, que é o nó de menor custo
            noAtual = (No) abertos.get(0);
            abertos.remove(noAtual);

            //verifica se o elemento retirado é o nó destino
            if (noAtual == destino) {
               // tela.marcaDestinoArvore(destino.getIdentificador());
                return constituiRota(destino);
            }
            //busca os sucessores do nó atual
            ArrayList<Object> sucessores = ControleLinks.getSucessores(noAtual);      

            for(int i=0; i < sucessores.size(); i++){
                No sucessor=(No)sucessores.get(i);
                //verifica se o nó sucessor já esta em alguma lista, se não, é adicionado na lsita de abertos
                if(!(abertos.contains(sucessor)) && !(fechados.contains(sucessor))){
                        //calcula distância da origem até o sucessor (G)
                        ControleNos.calculaDistanciaAcumulada(sucessor, noAtual);
                        //insere o pai(predecessor) para permitir rastrear o caminho de volta
                        sucessor.setPredecessor(noAtual);
                        //inclui o sucessor na lista de nos abertos pra ser verificado futuramente
                        abertos.add(sucessor);
                }else{
                    //se o nó já estiver na lista de abertos
                    //verifica se a distância da origem até esse sucessor é menor do que a do nó inicial
                    if (abertos.contains(sucessor)) {
                        if (sucessor.getDistanciaAcumulada() < noAtual.getDistanciaAcumulada()) {
                            //atualiza o pai e recalcula a destancia acumulada
                            ControleNos.calculaDistanciaAcumulada(sucessor, noAtual);
                            sucessor.setPredecessor(noAtual);
                        }
                    } else {
                        //o sucessor já foi fechado mais poderia ser uma escolha mais adequeda
                        //apenas atualiza o predecessor do nó atua;
                        double distancia=sucessor.getDistanciaAcumulada()+ControleLinks.getDistanciaReal(noAtual,sucessor);
                        if(distancia< noAtual.getDistanciaAcumulada()){
                            noAtual.setPredecessor(sucessor);
                            ControleNos.calculaDistanciaAcumulada(noAtual,sucessor);
                        }

                    }
                }
            }
           
        
            //adicona o nó atual na lista de fechados pois ele já foi verificado.
            fechados.add(noAtual);
        }
        return null;
    }

  //apartir do destino é possível descobrir a rota até ele percorrendo os predecessores
  private static ArrayList<No> constituiRota(No destino){
      ArrayList<No> melhorCaminho = new ArrayList();
      melhorCaminho.add(destino);
      No predecessor=destino.getPredecessor();
      while(!(predecessor==null)){
          melhorCaminho.add(predecessor);
          predecessor=predecessor.getPredecessor();

      }
      return melhorCaminho;
  }

   
   // este metodo é utilizado para receber as entradas, porcessar, e retornar a saída para o usuário
    public static void executa(int idorigem,int iddestino,limite.Apresentacao apresentacao) {
        tela=apresentacao;
        No origem=LocalizadoraDeNos.busca(idorigem);
        No destino=LocalizadoraDeNos.busca(iddestino);
        ArrayList<No> rota = AEstrela(origem,destino);
        if(rota==null){
            System.out.println("Algoritmo não foi capaz e idetificar o melhor caminho!");
            return;
        }
        //preencge campo menor distância
        tela.insereMelhorDistânciaAEstrela(ControleNos.distancia(rota));
        //apresentação dos resultados na tela
        marcaDistancias();
        tela.atualiza();
        marcaCaminhoMinimo(rota);
        tela.atualiza();
    }

    //utilizado para destacar o caminho escolhido na tela
    private static void marcaCaminhoMinimo(ArrayList<No> rota) {
        for (int i = 0; i < rota.size(); i++) {
            try {
                No origem = (No) rota.get(i);
                No destino = (No) rota.get(i + 1);
                tela.marcaCaminho(origem.getIdentificador(), destino.getIdentificador());
            } catch (Exception e) {
            }
        }
    }

    //utilizado para marcar o tamanho de cada link na tela
    private static void marcaDistancias(){
        ArrayList<Link> links = LocalizadoraLinks.getLista();
        for(int i = 0; i < links.size(); i++){
            Link l=(Link)LocalizadoraLinks.getLink(i);
            No origem=l.getOrigem();
            No destino=l.getDestino();
            tela.registraDistancia(origem.getIdentificador(),destino.getIdentificador(),ControleNos.calculaDistancia(origem, destino));
        }
    }
}


